package randomthoughts.dp;

/**
 * @author tongchen
 * @create 2023-04-16 21:35
 */
public class ChangeExchange {
    public static void main(String[] args) {

    }

    /** LeetCode 518
     * 五部曲：1.dp[i]代表组成i的方法数 i代表要组成的数; 2.递推公式：dp[i]+=dp[i]-nums[j]];3.初始化 ：默认dp[0]=1;4. 遍历顺序：求组合数，要先遍历
     * 物品，再遍历容量
     * @param amount
     * @param counts
     * @return
     */
    public static int change(int amount ,int[]counts){
        //创建dp数组
        int[]dp=new int[amount+1];
        dp[0]=1;
        //先遍历物品，再遍历容量
        for (int i = 0; i <counts.length ; i++) {
            for (int j = counts[i]; j <=amount ; j++) {
                dp[i]+=dp[j-counts[i]];
            }

        }
        return dp[amount];
    }
}
